package main

func main() {
	
}

//给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
//
// 示例 1:
//
// 输入: 2
//输出: 1
//解释: 2 = 1 + 1, 1 × 1 = 1。
//
// 示例 2:
//
// 输入: 10
//输出: 36
//解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
//
// 说明: 你可以假设 n 不小于 2 且不大于 58。
// Related Topics 数学 动态规划


//leetcode submit region begin(Prohibit modification and deletion)
// 数学归纳法
func integerBreak(n int) int {
	result := 1
	if n < 4 {
		return n - 1
	}
	for n > 4 {
		n -= 3
		result *= 3
	}
	return result * n
}
//leetcode submit region end(Prohibit modification and deletion)

// 动态规划
// 将 i 拆分成 j 和 i−j 的和，且 i−j 不再拆分成多个正整数，此时的乘积是 j * (i-j)j×(i−j)；
// 将 i 拆分成 j 和 i−j 的和，且 i-j 继续拆分成多个正整数，此时的乘积是 j * dp[i−j]。
func integerBreakDP(n int) int {
	dp := make([]int, n + 1)
	// dp[0] = dp[1 = 0
	for i := 2; i <= n; i++ {
		cmax := 0
		for j := 1; j < i; j++ {
			cmax = max(cmax, max(j * (i - j), j * dp[i - j]))
		}
		dp[i] = cmax
	}
	return dp[n]
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}